This application claims the priority of German patent document no. 10 2008 050 951.5-54, filed Oct. 10, 2008, the disclosure of which is expressly incorporated by reference herein.
The invention relates to the planning of flight routes for aircraft. In particular, the invention relates to the determination of cost-minimized routes for low-flying military transport planes.
Modern airplanes frequently cannot be controlled without the aid of automatic and autonomous onboard systems. Every day, civil as well as military pilots use systems for carrying out task segments. These systems permit pilots to concentrate on critical tasks for which it is not yet feasible (or accepted) to replace human thought and action.
These systems are developed not only for the purpose of comfort but also for safety reasons. Flying in military planes is becoming increasingly complex: Pilots are under more and more pressure, and find themselves in stressful situations. Combat missions are complicated; moreover, the countermeasures of a possible enemy are more complex and more effective. Since weapons have also become more destructive, the consequences of a pilot's error are more critical than ever. It is therefore the goal of technical onboard support systems to spare the crew the implementation of repetitive tasks, so that pilots will be able to concentrate on the significant aspects of their missions. For example, the distance from an obstacle can be computed when the delay between two radar echoes is known. However, pilots cannot be expected to compute the distances. Nowadays, automatic onboard systems compute such a distance, and pilots decide how to utilize the information.
It may be of interest to military planes to fly low in threatened areas because the terrain protects the airplane from detection by a radar or SAM (Surface to Air Missile) station. A low level flight (LLF) is a stressful phase. In comparison to a flight at high altitude, the pilot will encounter more obstacles for which his evading maneuver possibilities are limited. In addition, since the visual range is more limited in the case of a low level flight than when flying at a greater altitude, obstacles will appear more suddenly.
For this phase of the flight, which requires high concentration, an auto-router is helpful for pilots. Even if a pilot would instinctively fly in valleys and not over peaks, it is difficult for him to decide which valley may be the best. Such a task of determining the best valley is a typical task that can be carried out by a computer, provided there exists a model of the aircraft and of the topographical environment and its risks which defines the criteria for a good route. An auto-router can support the pilot by suggesting the optimal route between given points.
Furthermore, the processes and systems for route planning described herein can also be used in so-called unmanned air vehicles (UAV). In such air vehicles, an onboard computer independently makes decisions concerning the flight control on the basis of the determined flight route. Furthermore, a use for unmanned ground vehicles (UGV) is also conceivable.
The planning of a low level flight constitutes a stressful phase for pilots. This applies to jet pilots but particularly also to pilots of transport planes. Among other things, this is connected with the dynamics of transport planes. A typical combat plane can fly up to 2,500 km/h, whereas C-130J a transport plane can fly only up to 645 km/h. At maximal speed, the C-130J transport plane therefore requires 3.8 times more time to traverse a certain region. It is not only the speed that is lower for transport planes than for jet planes, but also the climbing abilities. However, transport planes are not only less easy to maneuver (i.e., they have fewer possibilities at their disposal of evading a dangerous object more rapidly); they are also larger, which makes them easier to recognize or detect. Because of the larger surface, transport planes also to reflect radar signals better than jet planes. Furthermore, the propeller blades reflect the signal in a persistently unmistakable manner which, in addition, makes the airplane clearly identifiable by radar systems.
When flying within the scope of low level missions, transport planes often land on unprepared landing strips which, in addition, allow only short approach possibilities. Tasks of this type, combined with the increased radar detectability, make it necessary for the airplane to fly even lower than a jet plane. Consequently, the transport plane is increasingly exposed to mobile risks, such as machine guns and launchers. In addition, the airplane is visible longer because is flies more slowly in low level flight.
In the present patent application, a process and a system are suggested for determining a flight route between starting and end points for a predefined chart with several types of threats. The determined flight route is to be selected such that it minimizes the occurring risks and, if possible, takes into account a given flight duration. In this case, the various risks can be quantified as a component of costs. The costs of a route can be modeled, for example, by a heuristic function, taking into account, among others, the altitude of the terrain, the position and the type of the enemy's radar stations, the positions of no-fly zones and additional parameters which have an influence on risks of the route. The costs of a certain route may therefore represent the risks of the route. The higher the cost, the more dangerous the route. The risks may be known ahead of time and may, for example, be the result of a visibility calculation for the airplane. However, the risks may also originate from randomly spread-out threats.
This problem is one of optimization. No systems or processes capable of computing a route with an adequately high precision within a sufficiently brief period of time are known from the state of the art. This computation time period should be so short that a computation can take place onboard the aircraft. It is therefore an object of the present application to provide a process and a system which, while the runtimes are reduced, determine a flight route for an aircraft that is as cost-optimal as possible.
According to one aspect, the invention relates to a process for planning a cost-minimized flight route for aircraft between a starting point and an end point. The aircraft may, for example, be civil or military airplanes or helicopters. The invention can also be used for unmanned aircraft, such as UAVs, drones, cruise missiles or rockets. Furthermore, the invention can also be used for vehicles in general. Particularly for so-called unmanned ground vehicles (UGVs), limitations of the vehicle with respect to its track angle or its turning circle can be taken into account by means of the process according to the invention. The invention is particularly suitable for the planning of flight routes of low-flying military transport planes. The flight route is determined taking into account the costs associated with the flight route. In addition, limitations of the flight route which are the result of characteristics of the aircraft are to be taken into account.
In one step, the process according to the invention determines a raster set which comprises topographical points between the starting point and the end point. There are, for example, topographical maps and charts concerning the region over which the flight is to take place. These maps can be scanned or digitized at certain spots, (i.e., at certain area coordinates). The scanning values, which are also called raster points here, will then form the raster set. Each raster point, in addition to the area coordinates (x, y), may also contain information concerning the topographical height z of the earth's surface at this scanning point.
When defining the scanning rate, attention is preferably paid to the fact that the number of raster points in the raster set is adapted to the minimal turning radius of the aircraft. Since, despite the quantization of the topographical conditions, it should further be possible to realistically simulate the flight path of an aircraft, the rastering of the region should be sufficiently fine in order to be able to define transitions between raster points which can describe the minimal turning circle or turning radius of the aircraft. On the other hand, the rastering should also not be too fine because otherwise the computing time of a cost-minimized flight route would increase.
In addition, the process determines costs associated with the raster points of the raster set. These costs may, for example, be flying costs occurring when flying over the raster point. Particularly in the case of military applications, the costs may also quantify threat risks for the aircraft. Typically, the costs are dependent on the area coordinates (x, y) of the raster point as well as on its topographical height z. However, in addition, the costs may also depend on the flight altitude of the aircraft. This flight altitude corresponds at least to the topographical height of the raster point. For reasons of simplification, in the following, the topographical height of the raster point as well as the flight altitude of the aircraft are indicated by the variable z. The meaning of z is in each case provided by the context.
In a further step, the process determines N nodes for each raster point of at least a subset of the raster set. The N nodes are associated with approach directions of the raster point by the aircraft. Furthermore, as a function of the approach direction, possible take-off directions of the raster point are defined. Finally, the possible take-off directions are defined while taking into account the turning radius of the aircraft. In other words, N nodes can be assigned to a raster point, which in each case correspond to an approach direction of the raster point. In the following, these nodes are also called direction nodes which may in each case represent, for example, an approach direction of the raster point. For defining possible approach directions, a complete angle of 360 degrees is divided into N subangles, each of the N subangles corresponding to an approach direction. Preferably, but not necessarily, the division into N subangles takes place in a uniform manner.
As mentioned above, possible take-off directions may be assigned to an approach direction. By means of such an assignment, it becomes possible to take into account the limitations of an aircraft with respect to its horizontal turning circle. In an embodiment, N direction nodes are assigned to a raster point N, which direction nodes each correspond to an approach direction. For each of these approach directions, M possible take-off directions can then be defined which correspond, for example, to a straight-line continued flight, a right turn or a left turn.
The approach directions and the take-off directions typically define transitions between raster points and/or their associated direction nodes. Expressed in terms of graph theory, these transitions may be understood as edges of a graph. In this case, it is not absolutely necessary for a transition from a raster point to take place only to directly adjacent raster points. Within the scope of a transition there may also be a “flying over” raster points.
Finally, the process according to the invention determines the cost-minimized flight route between the starting point and the end point by means of a shortest path algorithm. In this case, only the k most cost-effective nodes are taken into account for a raster point, k being smaller than N. The shortest path algorithms may be standard algorithms, such as the Dijkstra algorithm, A* algorithm and/or the Bellmann-Ford algorithm.
According to an aspect of the invention, these algorithms are modified such that they do not take into account all possible nodes of the graph but only the k most cost-effective nodes for each raster point. In other words, only the k most cost-effective approach directions are permitted in a raster point. All additional approach directions will then no longer be pursued in the shortest path algorithm. As a result, the runtime of the shortest path algorithm can be reduced. The acceleration factor is obtained from the ratio of N to k. On the other hand, under certain circumstances, the cost-optimal flight route between the starting point and the end point can theoretically be determined further.
In addition, it should be taken into account that the described process can be used not only for determining a flight route from a certain starting point to a certain end point. As a function of the selected shortest path algorithm, the shortest flight route can also be determined from a starting point to all possible end points of the raster set or even from all possible starting points to all possible end points.
As mentioned above, the costs associated with a raster point may take into account a threat risk to the aircraft. In this case, the line of sight starting from the raster point and/or the presence of surface-to-air missiles and/or the presence of radar stations may represent a threat risk. Particularly in connection with radar stations, it should be taken into account that interactions exist between the different threat risks with respect to one another and the topographical environment. Thus, although a radar station may be present, a low threat risk may exist at certain raster points because, at these raster points, the radar signal is shielded by a mountain or another obstacle. This information can frequently be determined ahead of time and therefore be combined in a cost matrix C(x, y, z).
Thus, for example, the presence of a launching station for surface-to-air missiles at a location (x, y) represents a threat in certain surroundings of this location. This threat could decrease, for example, with the distance from this location (x, y). On the other hand, the cost matrix may also depend on the flight altitude z of the aircraft. In particular, an aircraft can also be detected more easily by a radar station at a higher flight altitude. Finally, so-called “no-fly” zones can also be detected by means of the cost matrix C(x, y, z). These could be taken into account, for example, by the defining of (prohibitively) high cost values in the “no-fly” zones (x, y, c). In addition, so-called “must-fly” zones or flight corridors can also be taken into account in the cost matrix.
Furthermore, the flight comfort could also be taken into account in the costs. Thus, for example, changes of the flight path (i.e., therefore particularly horizontal and/or vertical changes of the flight path) could be assigned higher costs because they have a negative effect on comfort. For example, because of the banking of the aircraft, the flying of a horizontal turn will reduce the crew's comfort. This can be particularly significant during flights with injured persons.
According to an aspect of the invention, the costs may depend on the flight altitude of the aircraft. Costs are typically associated with the individual raster points. The costs of the transitions between two raster points can then be determined therefrom, for example, by integrating the cost function C(x, y, z) by way of the transition. When the costs depend on the flight altitude of the aircraft, flight altitude along the transition may also be included in the integral. In this case, the minimal flight altitude which in each case is possible at the topographical height of a raster point, could, for example, also be taken into account. Furthermore, the possible rate of vertical descent of the aircraft could also be taken into account.
As mentioned above, the possible take-off directions of a direction node preferably define a transition from a current raster point to a raster point that follows. This means that the take-off directions define a transition from a direction node of a current raster point to a direction node of a raster node that follows. In this case, there may be a “flying over” additional raster nodes in the case of the transition. The costs of the transition will then preferably depend on the costs of the raster points adjoining the transition and on the time in which the airplane flies through the transition. Summarizing, the nodes which are associated with the raster points, the possible transitions between these nodes and the costs of the transitions, can be understood to be nodes, edges and weights which define a weighted graph.
It should be noted that, in a preferred embodiment, only the geographic area coordinates of a raster point and its associated approach directions, but not the flight altitude of the aircraft, define nodes for determining the cost-minimized flight route by means of the shortest path algorithm. In other words, the flight altitude of the aircraft or the topographical height of the raster points is not taken into account as a separate dimension within the shortest path algorithm. On the contrary, these altitude components are preferably considered within the cost matrix C(x, y, z). The flight altitude and the topographical height therefore influence the cost-minimized flight route by way of the costs of the transitions.
In a preferred embodiment, three possible take-off directions are defined for each node: A straight-line take-off direction, a take-off direction extending to the left and a take-off direction extending to the right. In this case, the take-off directions extending to the left and the right define a certain change of direction relative to the approach direction, which can generally be described by an angle. This angle may amount, for example, to 22.5 degrees with respect to the straight-line take-off direction. Such an angle is obtained, for example, when a complete circle (360 degrees) is divided into N subangles equivalent to 16. In this case, N possible approach directions equivalent to 16 are also defined. For this constellation, a value of k=3 supplies satisfactory search results. Consequently, a reduction of the runtime by more than a factor of 5 is achieved, the search results furthermore being quasi-optimal. By means of such a runtime reduction, it becomes possible to newly compute flight routes in real time. This allows a pilot to continuously adapt his flight route to new conditions so as to reduce the risk of enemy fire.
The invention further comprises a system for determining a cost-minimized flight route for aircraft between a starting point and an end point, taking into account costs associated with the flight route and limitations of the flight route caused by the aircraft. The system comprises computing devices for determining the raster set which comprises possible topographical locations between the starting point and the end point. The system further comprises computing devices for determining costs associated with the raster points of the raster set, and computing devices for determining N nodes to each raster point of at least one subset of the raster set. The N nodes are associated with approach directions to the raster point by the aircraft. In addition, as a function of the approach direction, possible take-off directions of the raster point are defined, the possible take-off directions being defined while taking into account the turning radius of the aircraft. Finally, the system comprises computing devices for determining a cost-minimized flight route between a starting point and an end point by means of a shortest path algorithm, only the k most cost-effective nodes being taken into account for a raster point and k being smaller than N.
According to a further aspect, the invention comprises a flight control system for aircraft which comprises the above-described system. This may also be a mission preparation system which carries out the computation of suitable flight routes before a mission or at a ground station or in a control airplane. This may be particularly significant in connection with UAVs. In addition, the invention relates to an onboard computer of a manned or unmanned air vehicle, which carries out the described process. Such an onboard computer typically comprises a memory, in which the described process is stored, and a processor, which carries out the described process steps. Thus, it is conceivable that, based on the determined flight route, an automatic or manual intervention takes place into the control of the air vehicle. Particularly in the case of unmanned air vehicles, such as drones or missiles, new knowledge concerning threat risks could thus be taken into account close to real time in the flight control.
Another problem when determining an optimal flight route is taking into account maximum possible climb and descent rates of an aircraft. Thus, according to a further aspect, the invention relates to a process for planning a cost-minimized flight route between a starting point and an end point for aircraft in low level flight while taking into account costs as a function of the flight altitude and limitations of a climb rate or of the vertical turning radius caused by the aircraft. In a step, the process determines a node set between the starting point and the end point. In addition, the topographical height is determined for nodes of the node set. In a further step, costs are determined which are associated with the nodes of the node set and which depend on the flight altitude of the aircraft. Furthermore, a cost-minimized route section between the starting point and a current node is determined by means of a shortest path algorithm, in which case a minimally possible flight altitude—taking into account the flyable climb rates and vertical turning radii—which is caused by the terrain over which the flight takes place, is assumed at the nodes of the route section for determining the costs of the route section.
In a subsequent step, it is recognized that the aircraft cannot reach the topographical height of the current node starting from the flight altitude at the preceding node of the route section. In this case, corrected costs of the route section are determined. This takes place while taking into account the climb rate or the vertical turning radius of the aircraft and the minimally possible flight altitude to be reached at the current node. This process is continued while taking into account the corrected costs of the route section until the current node corresponds to the end point.
Also in this process, the statements can be used which were made above concerning the used terms. However, it should be noted that in this process nodes do not necessarily have to be direction nodes in the above-described sense. On the contrary, the described backward-directed correction of the costs of a route section can be applied to arbitrarily defined nodes and graphs.
In a preferred embodiment, the process further comprises the step of determining a raster set which comprises possible topographical points between the starting point and the end point. In addition, the process determines N nodes associated with a raster point of the raster set, the N nodes being associated with approach directions of the raster point by the aircraft. Further, as a function of the approach direction, possible take-off directions of the raster point are defined, the possible take-off directions being defined while taking into account the turning radius of the aircraft. In other words, in this case, the process concerning the backward-directed correction of the costs of a route section is applied to the above-explained model of the topographical region and of the possible flight paths of the aircraft.
In this case, when determining the most cost-effective route section also only the k most cost-effective nodes associated with a raster point are taken into account, k being smaller than N. As explained above, as a result, a reduction of the runtime of the used shortest path algorithm can be achieved. This is particularly advantageous because higher computing times which are the result of the backward-directed correction of the costs of a route section can thereby be compensated. When combined, the two processes further permit runtimes which are reduced in comparison to standard shortest path algorithms. On the other hand, because of the backward cost correction, the climb rate of an aircraft can also be taken into account when determining a flight route, which cannot be achieved by means of shortest path algorithms from the prior art. This improves the modeling of the costs.
As mentioned above, the costs can take into account a threat risk to the aircraft. Such a threat risk may be connected, for example, with the line of sight starting from the raster point or node point, the presence of surface-to-air missiles and/or the presence of radar stations. Naturally, other factors, such as fuel consumption, may also enter into the cost function.
In a preferred embodiment, a node is defined by the geographic area coordinates of a spot on the earth's surface. With respect to the search space of the shortest path algorithm, the nodes of the weighted graph will then be defined by the geographic area coordinates of a node. In contrast, the flight altitude of the aircraft would not be entered into the definition of the nodes of the weighted graph. The shortest path algorithms may, for example, be the Dijkstra algorithm, the A* algorithm and/or the Bellmann-Ford algorithm. The latter algorithms are known to those skilled in the art.
According to a further aspect of the invention, the corrected costs of the route section can be determined by the following process steps. First, corrected minimally possible flight altitudes of the aircraft are determined at preceding nodes while taking into account the climb rate of the aircraft and the minimally possible flight altitude to be reached at the current node. Then the costs associated with the preceding nodes are determined while taking into account the corrected minimally possible flight altitudes of the aircraft. In other words, it is determined at which altitude the aircraft would have flown at preceding nodes had the pilot known that he had to have reached a certain flight altitude at the current node in order to overcome the later appearing obstacle. These newly determined flight altitudes will then lead to corrected costs C(z) at these node points.
On the basis of these corrected costs, the corrected costs of the route section to the current node will then be computed. When a constant climb rate is assumed, the minimally possible flight altitude at a node will then be obtained from the minimally possible flight altitude at the node that follows, minus the product from the climb rate and the geometric distance of the two nodes.
In connection with the determination of the corrected costs of a route section, reference is made to the above statements concerning the determination of transition costs. The costs of the transitions between node points can be determined from the integral of the cost function C(x, y, z) “flown over” by a transition. For determining the corrected costs of a route section, the respective costs of the transitions between the sequence of node points can then be added up.
According to a further aspect, the invention relates to a system for determining a cost-minimized flight route between a starting point and an end point for aircraft in low-level flight while taking into account costs dependent on the flight altitude and limitations of a climb rate caused by the aircraft. The system comprises devices for determining a node set between the starting point and the end point and devices for determining the topographical height of the nodes of the node set. In addition, the system comprises devices for determining costs associated with the nodes of the node set, which costs depend on the flight altitude of the aircraft.
The system further comprises devices for determining a cost-minimized route section between the starting point and a current node by means of a shortest path algorithm, a minimally possible flight altitude being assumed at the nodes of the route section for determining the costs of the route section. The system further comprises devices for recognizing that the aircraft cannot reach the topographical height of the current node starting from the flight altitude at the preceding node of the route section. For this case, the system comprises devices for determining corrected costs of the route section while taking into account the climb rate or the vertical turning radius of the aircraft and the minimally possible flight altitude to be reached at the current node.
The invention further relates to a flight control system for aircraft which comprises the just described system. In addition, the invention relates to an onboard computer of a manned or unmanned air vehicle which implements the above-explained process with respect to the backward-directed correction of the costs of a route section.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings.